// https://www.lintcode.com/problem/intersection-of-two-arrays/my-submissions

class Solution {
public:
    /**
     * @param nums1: an integer array
     * @param nums2: an integer array
     * @return: an integer array
     */
    vector<int> intersection(vector<int> &nums1, vector<int> &nums2) {
        
        // 法一：set/hashmap
        
        
        // vector<int> result;
        // set<int> set1(nums1.begin(), nums1.end());
        // set<int> set2(nums2.begin(), nums2.end());
        // set<int>::iterator it = set1.begin();
        // for (; it != set1.end(); ++it)
        // {
        //     if (set2.find(*it) != set2.end())
        //     {
        //         result.push_back(*it);
        //     }
        // }
        // return result;
        
        // map<int, bool> record_map;
        // map<int, bool> result_map; //减少查询时的时间复杂度
        // vector<int> result;
        // for (int i = 0; i < nums1.size(); ++i)
        // {
        //     record_map[nums1[i]] == true;
        // }
        // for (int i = 0; i < nums2.size(); ++i)
        // {
        //     if (record_map.find(nums2[i]) != record_map.end() && result_map.find(nums2[i]) == result_map.end())
        //     {
        //         result_map[nums2[i]] = true;
        //     }
        // }
        // for (map<int, bool>::iterator it = result_map.begin(); it != result_map.end(); ++it)
        // {
        //     result.push_back(it->first);            
        // }
        // return result;
        
        
        // 法二：排序之后双指针
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        set<int> result_set;
        vector<int>::iterator it1 = nums1.begin();
        vector<int>::iterator it2 = nums2.begin();
        while (it1 != nums1.end() && it2 != nums2.end())
        {
            if (*it1 < *it2) it1++;
            else if (*it1 > *it2) it2++;
            else
            {
                result_set.insert(*it1);
                it1++;
                it2++; //别忘记了
            }
        }
        return vector<int>(result_set.begin(), result_set.end());
        
        
        // 法三：排序之后二分法
        // 二分查找数组二的元素在不在数组一中
    }
};